package com.mlh.hash;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 缪林辉
 * @date 2024/8/13 14:59
 * @DESCRIPTION
 */
//给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
// 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
// 输入：nums = [100,4,200,1,3,2]
// 输出：4
// 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
public class 最长连续序列 {
    // 如果已知有一个 x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，
    // 那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。
    // 那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，这样就不会重复查找一个连续序列。
    public int method1(int[] nums) {
        int res=0;
        Set<Integer>set=new HashSet<>();
        //将数组元素放入set中，顺便去重
        for(int num:nums){
            set.add(num);
        }
        for (int num:set){
            if(!set.contains(num-1)){//判断跳过
                int longest=1;
                while (set.contains(num+1)){
                    longest++;
                    num++;
                }
                res=Math.max(res,longest);
            }
        }
        return res;
    }
    public int practice(int[] nums) {
        HashSet<Integer>set=new HashSet<>();
        int res=0;
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for (int num:set){
            if(set.contains(num-1)){
                continue;
            }
            int len=1;
            while(set.contains(num+1)){
                ++len;
                ++num;
            }
            res= Math.max(res,len);
        }
        return res;
    }

}
